package 单链表;

public class BasicOperations {
    // push 插入
    // pop  删除
    // front: 从头
    // back: 从尾

    // 传入原链表的头结点和待插入元素
    // 返回值：头插后新链表的头结点
    public static ListNode pushFront(ListNode head, int val) {
        ListNode node = new ListNode(val);

        node.next = head;   // 让 node（新的头结点) 的下一个结点
                            // 是原来的头结点

        return node;
    }

    // 遍历打印链表
    public static void printLinkedList(ListNode head) {
        for (ListNode cur = head; cur != null; cur = cur.next) {
            System.out.printf("%d ", cur.val);
        }
        System.out.println();
    }

    // 头删
    // 需要的参数：以头节点为代表的待头删链表 —— ListNode head
    // 返回结果：以头节点为达四百的新的链表
    public static ListNode popFront(ListNode head) {
        if (head == null) {
            throw new RuntimeException("链表为空，不处理");
        }

        return head.next;
    }

    public static ListNode pushBack(ListNode head, int val) {
        ListNode node = new ListNode(val);

        if (head != null) {
            // 1. 找到最后一个结点
            ListNode last = head;
            while (last.next != null) {
                last = last.next;
            }
            // 循环结束后，last.next == null，说明 last 指向最后一个结点
            last.next = node;

            return head;
        } else {
            return node;
        }
    }

    public static ListNode popBack(ListNode head) {
        if (head == null) {
            throw new RuntimeException("链表为空，不处理");
        }

        if (head.next != null) {
            // 1. 找到倒数第二个结点
            ListNode last = head;
            while (last.next.next != null) {
                last = last.next;
            }
            // 循环结束时，last.next.next == null，说明 last 指向倒数第二个结点

            last.next = null;

            return head;
        } else {
            return null;
        }
    }

    public static void main(String[] args) {
        ListNode head = null;

        head = pushFront(head, 1);
        head = pushFront(head, 2);
        head = pushFront(head, 3);

        // 3 2 1
        printLinkedList(head);

        head = popFront(head);
        // 2 1
        printLinkedList(head);


        head = popFront(head);
        // 1
        printLinkedList(head);




        head = popFront(head);
        //
        printLinkedList(head);


        head = pushBack(head, 1);
        head = pushBack(head, 2);
        head = pushBack(head, 3);

        // 1 2 3
        printLinkedList(head);

        head = popBack(head);
        // 1 2
        printLinkedList(head);

        head = popBack(head);
        // 1
        printLinkedList(head);

        head = popBack(head);
        //
        printLinkedList(head);
    }
}
